The Transmission Control Protocol/Internetwork Protocol (TCP/IP) are two protocols that are designed to connect computer systems that use different operating systems and network technologies. Application or process data communicated by TCP/IP is “packetized” and as it passes through the four layers of the TCP/IP protocol suite. TCP traffic is typically generated from a source connected to a LAN e.g. Ethernet etc., and is aggregated through an Internet Protocol (IP) edge router to an access network that uses a different link layer technology such as Asynchronous Mode Transfer (ATM). (However, the access network need not necessarily be ATM, but could be IP everywhere, Ethernet everywhere etc.) Congestion at the edge router occurs when the bandwidth available in the access network cannot support the aggregated traffic generated from the LAN. While the access network may have its own traffic control mechanism, its effect terminates at edge routers e.g., the interface between two networks, and consequently, the end-to-end performance is not improved.
When congestion occurs in a packet switched system at the edge router, a packet dropping policy for dropping packets in the packet buffer must be implemented. With the introduction of differentiated services in the Internet, Internet Service Providers (ISP's) can differentiate their services (diffserv) such that a user can select the packet delay or packet loss class that the user's packets will experience.
For example, with diffserv, the user can select different service classes, with a low delay or low packet loss probability at a high cost, medium delay or medium packet loss probability at an average cost, and high delay or high packet loss probability at a low cost.
Thus, the Internet Service Providers (ISPs) can differentiate their services, and implement different pricing strategies, such that a better class of service will cost the end user more money.
Since this value is relative, the user will experience very good service during non-busy hours, and bad service in the busy hours, for the same delay or packet loss probability class. Indeed, the selection is relative—and therefore, in non-busy hours all users will choose the inexpensive high delay or high packet loss service class since it will at that moment, deliver good service (in absolute terms).
Since, in non-busy hours, the network will not be loaded heavily and differences in the delay or packet loss service classes may be so small that all users would tend to choose the cheapest high delay or high packet loss probability service class that will offer only marginally a higher delay than the expensive low delay or packet loss probability class service, the overall revenue for the ISP is lower in non-busy hours.
Prior art solutions for addressing the issue of dropping packets in a packet buffer include Rear Dropping, Front Dropping, Priority Dropping, and Random Drop.
Rear Dropping is where packets are dropped from the rear of the buffer (i.e., to drop incoming packets until the buffer is no longer full)—with no regard as to the priority or importance degree of the packet.
Front Dropping drops packets from the front of the queue, which improves both average buffering delay and the overall loss performance for time-constrained traffic, but which again, has no regard as to the priority or importance degree of the packet.
Priority Dropping involves marking incoming packets with a priority marker (establishing classes of packets) and dropping low priority packets. Although this policy decreases the probability of dropping high priority packets, it accomplishes this result at the expense of increasing the probability of dropping low priority packets.
Random Drop, also known as Random Early Detection or Random Early Drop (RED) (see “Random Early Detection Gateways for Congestion Avoidance”, Sally Floyd and Van Jacobsen, 1993 IEEE/ACM Transactions on Networking), calculates a drop probability based on the queue size (or level of congestion), and will assign a large drop probability for large queue sizes, and small drop probabilities to small queue sizes. Mostly, the drop probability increases linearly with the level of congestion. This means that in times of low congestion, the queues are small, and thus, also the drop probabilities. This results in the fact that there is almost no difference between the different packet types/priorities: all packets have small drop probabilities. Here, the importance degree is taken into account: packets with a lower importance degree get for instance, a drop probability which is 5 times larger compared to the packets with a high importance degree.
Specifically, the RED scheme drops packets before the buffer becomes saturated. The buffer is monitored and when the average buffer occupancy goes beyond a particular threshold, packets are dropped according to a random test (e.g. with a certain probability which is a function of the average buffer occupancy (moving time average)), which causes TCP connections to cut their windows randomly. This is particularly effective to de-synchronize the windows. Specifically, in a FIFO-RED scheme, those connections that use the link more are likely to have more packets dropped and consequently, its corresponding window size-cut. This tends to reduce the bias for these higher rate connections. Because the RED algorithm allows the dropping of packets without regard to the characteristics of a flow, packets may be dropped in a flow that is critical for system performance but is not responsible for congestion in the system. Overall system performance will benefit by increasing drop probabilities for flows that are causing the congestion.
Other approaches have focused on preferences by certain users. That is, a flow owned by a preferred user can have a drop probability curve (i.e., higher-priority queue) with lower values as compared with a curve associated with a non-preferred user. As a result, flows belonging to a preferred user may benefit, but system performance is not enhanced.
However, the problem with all these approaches is that they only control packet loss and do not address revenues generated for the ISP. Specifically, irregardless of the type of packet drop policies which are implemented above, in non-busy hours, the user's choice of the cheapest high delay or high packet loss probability decreases the overall revenue for the ISP.
Accordingly, finding a way to drop packets such that low priority packets have a guaranteed non-negligible drop probability, or delay, such that service is better differentiated between the different service classes in both busy and non-busy hours, and the ISP can provide better “absolute” packet loss probability values or delay service values at increased revenues, is needed.